/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：分隔链表
 * 思路：遍历链表，小节点值的链表放置一堆，大节点值的链表放置一堆，最后再让小链表与大链表相连即可
 */
public class Test {
    public ListNode partition(ListNode head, int x) {
        // 遍历链表，将链表进行分割
        ListNode largeHead = new ListNode(-1);
        ListNode largeCur = largeHead;
        ListNode littleHead = new ListNode(-1);
        ListNode littleCur = littleHead;
        while (head != null) {
            int value = head.val;
            ListNode newNode = new ListNode(value);
            if (value < x) {
                littleCur.next = newNode;
                littleCur = newNode;
            } else {
                largeCur.next = newNode;
                largeCur = newNode;
            }
            head = head.next;
        }
        // 将两个链表链接起来
        littleCur.next = largeHead.next;
        return littleHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}